package com.leetcode.algorithm.y19.m04;

import java.util.HashSet;
import java.util.Set;

/**
 * leetcode-cn.com 
 * (TODO)219. 存在重复元素 II 
 * (TODO)220. 存在重复元素 III
 * 
 * @author: jie.deng
 * @time: 2019年4月28日 上午11:43:26
 */
public class MySolution0428 {
    
    /**
     * 219. 存在重复元素 II
     * 
     * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j
     * 的差的绝对值最大为 k。
     * 
     * 示例 1:
     * 输入: [1,2,3,1], k = 3 
     * 输出: true 
     * 
     * 示例 2:
     * 输入: [1,0,1,1], k = 1 
     * 输出: true 
     * 
     * 示例 3:
     * 输入: [1,2,1], k = 0 
     * 输出: false
     * 
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 结合使用滑动窗口和查找表，不断查找当前滑动窗口内有没有重复值。我们通过建立一个 record
        // 查找表，表中存的是窗口中的数，另外我们要注意的是，当窗口的大小 > k 的时候，我们要移除 record 中最左边的元素（保证我们窗口中有
        // <= k 个数）。        
        int l = 0;
        int r = l;
        Set<Integer> set = new HashSet<Integer>(k + 1);
        while (r < Math.min(k, nums.length - 1)) {
            if (!set.add(nums[r++])) {
                return true;
            }
        }
        while (r <= nums.length - 1) {
            if (!set.add(nums[r++])) {
                return true;
            }
            set.remove(nums[l++]);
        }
        return false;
    }
    
    /**
     * 220. 存在重复元素 III
     * 
     * 给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
     * 
     * 示例 1:
     * 
     * 输入: nums = [1,2,3,1], k = 3, t = 0
     * 输出: true
     * 示例 2:
     * 
     * 输入: nums = [1,0,1,1], k = 1, t = 2
     * 输出: true
     * 示例 3:
     * 
     * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
     * 输出: false
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.length == 0 || k == 0 || t < 0) {
            return false;
        }
        int l = 0;
        int r = l;
        Set<Integer> set = new HashSet<Integer>(k); // k个相邻的数
        while (r < Math.min(k, nums.length - 1)) {
            int cur = nums[r++];
            if (t == 0) {
                if (set.contains(cur)) {
                    return true;
                }
            } else {
                int min = Integer.MIN_VALUE + t >= cur ? Integer.MIN_VALUE : cur - t;
                int max = Integer.MAX_VALUE - t <= cur ? Integer.MAX_VALUE : cur + t;
                for (Integer num : set) {
                    if (num >= min && num <= max) {
                        return true;
                    }
                }
            }
            set.add(cur);
        }
        while (r <= nums.length - 1) {
            int cur = nums[r++];
            if (t == 0) {
                if (set.contains(cur)) {
                    return true;
                }
            } else {
                int min = Integer.MIN_VALUE + t >= cur ? Integer.MIN_VALUE : cur - t;
                int max = Integer.MAX_VALUE - t <= cur ? Integer.MAX_VALUE : cur + t;
                for (Integer num : set) {
                    if (num >= min && num <= max) {
                        return true;
                    }
                }
            }
            set.remove(nums[l++]);
            set.add(cur);
        }
        return false;
    }
    
}
